package src.leetcode.dp.medium_0647;

public class countSubstrings {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countSubstrings("aaa"));
    }
}

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        boolean [][]dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; i + j < n; j++) {
                if((s.charAt(j) != s.charAt(i + j))) continue;
                if (i < 2 || dp[i - 2][j + 1]) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
        return count;
    }
}
